package Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TopologicalSort {
    //拓扑排序
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("java基础");
        Vertex v3 = new Vertex("javaweb");
        Vertex v4 = new Vertex("数据库");
        Vertex v5 = new Vertex("Spring框架");
        Vertex v6 = new Vertex("微服务框架");
        Vertex v7 = new Vertex("实战项目");

        //描述图
        v1.edges = List.of(new Edge(v3));
        v2.edges = List.of(new Edge(v3));
        v3.edges = List.of(new Edge(v5));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v6));
        v6.edges = List.of(new Edge(v7));
        v7.edges = List.of();

        ArrayList<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4, v5, v6, v7));

        //统计每一个顶点的入度
        for (Vertex v : graph) {
            for (Edge edge : v.edges) {
                edge.linked.inDegree++;
            }
        }
        graph.forEach(vertex -> System.out.println(vertex.name + " " + vertex.inDegree));
        //将入度为0的加入到队列去
        LinkedList<Vertex> queue = new LinkedList<Vertex>();
        graph.forEach(vertex -> {
            if (vertex.inDegree == 0) {
                queue.offer(vertex);
            }
        });
        System.out.println("======");
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            //相邻顶点的入度减一
            poll.edges.forEach(v -> {
                v.linked.inDegree--;
                if (v.linked.inDegree == 0) {
                    queue.offer(v.linked);
                }
            });
        }
        LinkedList<String> stack = new LinkedList<>();
        graph.forEach(v -> {
            dfs(v, stack);
        });
        System.out.println(stack);
    }

    private static void dfs(Vertex v, LinkedList<String> stack) {
        if (v.status == 2) {
            return;
        }
        if (v.status == 1) {
            throw new RuntimeException("发现了环！");
        }
        v.status = 1;
        v.edges.forEach(l -> {
            dfs(l.linked, stack);
        });
        v.status = 2;
        stack.push(v.name);

    }


}
